package net.lainiao.leetcode;

import net.lainiao.leetcode.base.Common;
import net.lainiao.leetcode.base.ListNode;

import java.util.ArrayList;
import java.util.List;

public class LintCode104 {

    public static List<ListNode> getListNodes(){
        String data="[-10->-9->-9->-3->-1->-1->0->null,-5->null,4->null,-8->null,null,-9->-6->-5->-4->-2->2->3->null,-3->-3->-2->-1->0->null]";
        data="[-8->-8->-3->-2->0->2->2->3->3->null,-5->-3->1->null,-9->-7->-1->4->null,-10->-4->-4->-4->0->3->null,-2->4->null,-9->-6->-5->-5->-3->-3->-2->2->null,1->3->null,-8->-3->-2->1->3->null]";
//        data="[1,-1, 0, 0, 1, 1, 1, -2, 2]";
        data=data.replace("[","").replace("]","");
        data=data.replaceAll("->null","");
        String[] strs=data.split(",");
        List<ListNode> nodes=new ArrayList<>();
        for(String str:strs){
            if(str.equals("null")){
                continue;
            }
            ListNode temRoot=null;
            ListNode current=null;
            String[] strDatas=str.split("->");
            for(String strData:strDatas){
                int val=Integer.parseInt(strData.trim());
                ListNode node=new ListNode(val);
                if(temRoot==null){
                    temRoot=node;
                    current=node;
                    continue;
                }
                current.next=node;
                current=node;
            }
            nodes.add(temRoot);
        }
        return nodes;
    }

    //合并K个排序列表
    public static void main(String[] args) {
            List<ListNode> list=LintCode104.getListNodes();
            LintCode104 code104=new LintCode104();
            ListNode root=code104.mergeKLists(list);
            Common.showListNode(root);

    }


    public ListNode mergeKLists(List<ListNode> lists) {
        if(lists==null||lists.size()==0){
            return null;
        }
        int size=lists.size();
        MyMinHeap myMinHeap=new MyMinHeap();

        for (ListNode node:lists){
            if(node!=null){
                myMinHeap.push(node);
            }
        }

        ListNode root=new ListNode(Integer.MIN_VALUE);
        ListNode cur=root;
        while (!myMinHeap.isEmpty()){
            ListNode temp=myMinHeap.pop();
            cur.next=temp;
            cur=cur.next;
            if(temp.next!=null){
                myMinHeap.push(temp.next);
            }
        }
        cur.next=null;
        return root.next;
    }

    class  MyMinHeap{
        private List<ListNode> nodes=new ArrayList<>();
        public void push(ListNode node){
            nodes.add(0,node);
            adjustNode(0);
        }

        private void adjustNode(int index) {
            int leftIndex=index*2+1;
            int rightIndex=index*2+2;
            int minIndex=index;
            if(leftIndex<nodes.size()&&nodes.get(leftIndex).val<nodes.get(index).val){
                minIndex=leftIndex;
            }

            if(rightIndex<nodes.size()&&nodes.get(rightIndex).val<nodes.get(minIndex).val){
                minIndex=rightIndex;
            }

            if(minIndex==index){
                return;
            }

            ListNode tem=nodes.get(index);
            nodes.add(index,nodes.get(minIndex));
            nodes.remove(index+1);
            nodes.add(minIndex,tem);
            nodes.remove(minIndex+1);
            adjustNode(minIndex);
        }

        public ListNode pop(){
            ListNode tem=nodes.get(0);
            nodes.remove(0);
            if(nodes.size()>0){
                buildHeap();
            }
            return tem;
        }

        private void buildHeap() {
            int size=nodes.size();
            for (int i = size/2-1; i>=0 ; i--) {
                adjustNode(i);
            }
        }




        public boolean isEmpty(){
            return nodes.size()==0;
        }

    }
}
